// https://www.lintcode.com/problem/letter-case-permutation/

public class Solution {
    /**
     * @param S: a string
     * @return: return a list of strings
     */
    public List<String> letterCasePermutation(String S) {
        // write your code here
        List<String> ret = new ArrayList<>();
        if (S.length() > 0) {
            List<String> perms;
            if (S.length() > 1) {
                perms = letterCasePermutation(S.substring(1));
            } else {
                perms = new ArrayList<>();
                perms.add(S);
            }
            for (int i = 0; i < perms.size(); ++i) {
                StringBuilder sb = new StringBuilder();
                Character c = S.charAt(0);
                sb.append(c);
                if (S.length() > 1) {
                    sb.append(perms.get(i));
                }
                if ((c >= '0') && (c <= '9')) {
                    ret.add(sb.toString());
                } else {
                    sb.setCharAt(0, Character.toLowerCase(c));
                    ret.add(sb.toString());
                    sb.setCharAt(0, Character.toUpperCase(c));
                    ret.add(sb.toString());
                }
            }
        } else {
            ret.add("");
        }
        return ret;
    }
}